#include <stdio.h> 
#include <stdlib.h> 
#include <math.h>
#include <time.h>
#include <limits.h>

#include <iostream>
#include <string>

#include <ctime>    
#include <cstdlib>
#include <math.h>

//Incluyo la clase Mersenne-Twister para la generación de números aleatorios
#include "mt.h"

using namespace std;
//using std::string;

typedef struct Cromosoma {
	int bit[8];	
	int fit;
}cromosoma;



int calcularFitness(Cromosoma c) {
	int fitness = 0;
	int contador = 0;
	for(int i=7; i>=0; i--){
	  fitness = fitness + c.bit[i] * pow(2,contador);
	  contador++;
	}
	return fitness;
}

/** Esta funcion es la encargada de inicializar la poblacion **/
//representacion: binaria, entera, real, permutacion
//metodoInicializacion: aleatorio, no aleatorio
int inicializarPoblacion(Cromosoma poblacion[10] , MersenneTwister *mt) {
	printf("Inicializando poblacion...\n");
	int i,j;
	for(i=0; i<10; i++){
		for(j=0; j<8; j++){			
			long r = (mt->genrand_int32() % 10) + 1;
			if (r <= 5) {				
				poblacion[i].bit[j] = 0;
			}
			else {
				poblacion[i].bit[j] = 1;
			}			
		}
		poblacion[i].fit = calcularFitness(poblacion[i]);
	}
	
	return 0;
}

int obtenerPrimerIndiceLibre(int parejas[10]){
	for(int k=0;k<10;k++){
	  if(parejas[k] == -1)
		return k;
	}
	return -1;	
}

int obtenerPrimerIndiceOcupado(int parejas[10]){
  for(int k=0;k<10;k++){
	  if (parejas[k] != -1)
		return k;
  }
  return -1;
}

//Seleccion por torneo
void seleccionPorTorneo(Cromosoma poblacion[10], int parejas[10]){
    //una vez formadas las parejas, el mejor de cada pareja lo copio en el lugar del peor
	int indice;
	for(int k=0; k<5; k++){
		indice = obtenerPrimerIndiceOcupado(parejas);
		if (indice != -1) {	
			if (poblacion[indice].fit > poblacion[parejas[indice]].fit){
				poblacion[parejas[indice]] = poblacion[indice];
			}
			else {
				poblacion[indice] = poblacion[parejas[indice]];
			}
			parejas[parejas[indice]] = -1;
			parejas[indice] = -1;
		}
	}
}


void imprimirParejas(int parejas[10]){
	cout <<"Parejas = ";
	for(int j=0; j<10; j++){
		cout << parejas[j] <<" ";
	}
	cout <<"\n";	
}



void armarParejas(int parejas[10], MersenneTwister* mt){
	//arreglo que contiene las parejas
	for(int k=0;k<10;k++){
	  parejas[k] = -1;
	}
	int r, indice;
	for(int k=0; k<10; k++){
		indice = obtenerPrimerIndiceLibre(parejas);
		if (indice != -1) {	
			r = (mt->genrand_int32() % 9) + 1;
			while(parejas[r] != -1){
				r = (r + 1) % 10;
			}
			parejas[r] = indice;
			parejas[indice] = r;
		}
	}
}

//Seleccion elitista... retorna solo 2??
void seleccion(Cromosoma poblacion[10], Cromosoma seleccionados[2]){
    int i,j;
	seleccionados[0].fit = -1;
	seleccionados[1].fit = -1;
	for(i=0; i<10; i++){
		if (poblacion[i].fit > seleccionados[0].fit){
			if(seleccionados[0].fit < seleccionados[1].fit)
				seleccionados[0] = poblacion[i];
			else
				seleccionados[1] = poblacion[i];
		}
		else 
			if(poblacion[i].fit > seleccionados[1].fit) {
				seleccionados[1] = poblacion[i];
			}			
	}
}

void cruzamiento(Cromosoma poblacion[2], Cromosoma cruzados[2], MersenneTwister* mt){
	long r = mt->genrand_int32() % 8;
	for(int i=0; i<8; i++){
		if(i<=r){
			cruzados[0].bit[i] = poblacion[0].bit[i];
			cruzados[1].bit[i] = poblacion[1].bit[i];
		}else{
			cruzados[0].bit[i] = poblacion[1].bit[i];
			cruzados[1].bit[i] = poblacion[0].bit[i];
		}
	}
	cruzados[0].fit = calcularFitness(cruzados[0]);
	cruzados[1].fit = calcularFitness(cruzados[1]);
}

void cruzamientoPoblacion(Cromosoma poblacion[10], int parejas[10], int probabilidad, MersenneTwister* mt){
	//una vez formadas las parejas,.....
	int indice;
	for(int k=0;k<10;k++){
		indice = obtenerPrimerIndiceOcupado(parejas);
		if (indice != -1) {	
			Cromosoma cruzados[2];
			Cromosoma aCruzar[2];
			aCruzar[0] = poblacion[indice];
			aCruzar[1] = poblacion[parejas[indice]];
			cruzamiento(aCruzar, cruzados,mt);
			poblacion[indice] = cruzados[0];
			poblacion[parejas[indice]] = cruzados[1];
			parejas[parejas[indice]] = -1;
			parejas[indice] = -1;
		}
	}
}

void mutacion(Cromosoma poblacion[10], int probabilidad, MersenneTwister*mt){
	long r;
	for(int i = 0; i < 10; i++){
		if((mt->genrand_int32() % 101) >= probabilidad ){
			r = (mt->genrand_int32() % 8);
			if(poblacion[i].bit[r] == 0)
				poblacion[i].bit[r] = 1;
			else
				poblacion[i].bit[r] = 0;
			poblacion[i].fit = calcularFitness(poblacion[i]);	
		}
	}	
}

void imprimirPoblacion(Cromosoma poblacion[10]){
	for(int i=0; i<10; i++){
		for(int j=0; j<8; j++){
			cout << poblacion[i].bit[j];
		}
		cout <<" ";
	}	
	cout << "\n fitness = \n";
	for(int i=0; i<10; i++){	
		cout << poblacion[i].fit <<" ";
	}
	cout <<"\n";
}


void imprimirPoblacion2(Cromosoma poblacion[2]){
	for(int i=0; i<2; i++){
		for(int j=0; j<8; j++){
			cout << poblacion[i].bit[j];
		}
		cout <<"\n";
		cout << "fitness = " << poblacion[i].fit <<"\n";
	}
}

void imprimirCromosoma(Cromosoma c){
	for(int j=0; j<8; j++){
		cout << c.bit[j];
	}
	cout <<"\n";
	cout << "fitness cromosoma = " << c.fit <<"\n";	
}


int obtenerMejorFitness(Cromosoma poblacion[10], Cromosoma &mejor){
	int mejorFitness = -1;
	for(int i=0; i<10; i++){
		if(poblacion[i].fit > mejorFitness){
			mejorFitness = poblacion[i].fit;
			mejor = poblacion[i];	
		}			
	}	
	return mejorFitness;
}

//obtenemos el mejor cromosoma y su indice
int obtenerIndiceMejorFitness(Cromosoma poblacion[10], Cromosoma &mejor){
	int mejorFitness = -1;
	int indice = -1;
	for(int i=0; i<10; i++){
		if(poblacion[i].fit > mejorFitness){
			mejorFitness = poblacion[i].fit;
			mejor = poblacion[i];	
			indice = i;
		}			
	}	
	return indice;
}

//obtenemos el peor cromosoma y su indice
int obtenerIndicePeorFitness(Cromosoma poblacion[10], Cromosoma &peor){
	int peorFitness = INT_MAX;
	int indice = -1;
	for(int i=0; i<10; i++){
		if(poblacion[i].fit < peorFitness){
			peorFitness = poblacion[i].fit;
			peor = poblacion[i];	
			indice = i;
		}			
	}	
	return indice;
}

//los 2 mejores nuevos pasan a la poblacion actual reemplazando los 2 peores viejos
void reemplazoStadyState(Cromosoma nueva[10], Cromosoma actual[10]){
	Cromosoma mejorNuevo;
	Cromosoma peorActual;
	Cromosoma aux;
	int indiceMejorNuevo;
	int indicePeorActual;
	//n es la cantidad de individuos a reemplazar. Este valor es aleatorio
	int n = 2;
	for(int i = 0; i < n; i++){	
		indiceMejorNuevo = obtenerIndiceMejorFitness(nueva, mejorNuevo);
		indicePeorActual = obtenerIndicePeorFitness(actual, peorActual);
		aux = actual[indicePeorActual];
		actual[indicePeorActual] = nueva[indiceMejorNuevo];
		nueva[indiceMejorNuevo] = aux;
	}
}

void copiarPoblacion(Cromosoma actual[10], Cromosoma nueva[10]){
	for(int j=0; j<10; j++){
		nueva[j] = actual[j];
	}
}

int main(){
	//inicializo la clase mt para las variables aleatorias
	MersenneTwister* mt;
	mt = new MersenneTwister();
	mt->init_genrand(time(NULL));


	int probabilidadMutacion = 80;
	int probabilidadCruzamiento = 20;
	Cromosoma nuevaPoblacion[10];
	Cromosoma poblacionActual[10];
	inicializarPoblacion(poblacionActual, mt);
	cout <<"poblacion inicial\n";
	imprimirPoblacion(poblacionActual);
	int mejorFitness = -1;
	Cromosoma mejorCromosoma;
	int cont = 0;
	//los individuos de la poblacion actual se van intercambiando en el reemplazo
	while(mejorFitness < 250){
		cout << "----------------iteracion----------------------- " << cont << "\n";
		copiarPoblacion(poblacionActual,nuevaPoblacion);
		int parejas[10];
		armarParejas(parejas,mt);
		imprimirParejas(parejas);
		seleccionPorTorneo(nuevaPoblacion, parejas);
		cout << "+++++seleccionados++++" <<"\n";
		imprimirPoblacion(nuevaPoblacion);
		armarParejas(parejas, mt);
		cruzamientoPoblacion(nuevaPoblacion, parejas, probabilidadCruzamiento, mt);
		cout << "+++++++++cruzados+++++++++" <<"\n";
		imprimirPoblacion(nuevaPoblacion);
		mutacion(nuevaPoblacion,probabilidadMutacion, mt);
		cout << "+++++++++mutados+++++++++" <<"\n";		
		imprimirPoblacion(nuevaPoblacion);
		cout << "+++++++++reemplazo+++++++++" <<"\n";
		cout << "|||||||||||||||||||||||||||||||||||||||||||||||||||||||" <<"\n";
		imprimirPoblacion(poblacionActual);
		reemplazoStadyState(nuevaPoblacion, poblacionActual);		
		cout << "+++++++++nueva Pob+++++++++" <<"\n";
		imprimirPoblacion(poblacionActual);
		mejorFitness = obtenerMejorFitness(poblacionActual,mejorCromosoma);
		cout << "el mejor fitness es " << mejorFitness<<"\n";
		cont++;
	}

	cout << "el mejor cromosoma es" <<"\n";
	imprimirCromosoma(mejorCromosoma);
	return 1;
}
